#pragma once
#include"Node.h"
#include<vector>
#define Size 100
/*Node declaration
template<typename T>
struct BiTreeNode
{
	T data;
	struct BiTreeNode<T> *pLChild;
	struct BiTreeNode<T> *pRChild;
};*/

template<typename T>
class StackNode
{
public:
	BiTreeNode<T> *pNode;
	int tag;
};

template<typename T>
class BiTree
{
public:
	BiTree(void);
	~BiTree(void);
	void CreateBiTree();
	void PrintTree();

	/* Recursive implementation*/
	void PreOrderTraversal();
	void InOrderTraversal();
	void PostOrderTraversal();

	// Level traversal
	void LevelOrderTraversal();

	int GetNodesNum();
	int GetLeafNum();
	int GetNotLeafNum();
	int GetDepth();
	void PrintAllPaths();
	void PrintAllPathsCore(BiTreeNode<T> *pRoot, std::vector<T>& path);
	void FindPath(const T &value);
	void FindPathCore(BiTreeNode<T> *pRoot, std::vector<T>& path, const T& value);
	/* Nonrecursive implementation.But Maybe overflow */
	void PreOrder1();
	void PreOrderOpt();
	void InOrder1();
	void PostOrder1();

	/*Nonrecursive implementation. Good*/
	void InOrder2();
	void PreOrder2();
	void PostOrder2();
	int GetDepthNonRecur();
	int CaculateAreaOfTree();

private:
	BiTreeNode<T>* CreateBiTreeNodes();
	void PreOrderTraversal(BiTreeNode<T> *pNode);
	void InOrderTraversal(BiTreeNode<T> *pNode);
	void PostOrderTraversal(BiTreeNode<T> *pNode);
	int NodesNumGetter(BiTreeNode<T> *pNode);
	int LeafNumGetter(BiTreeNode<T> *pNode);
	int NotLeafNumGetter(BiTreeNode<T> *pNode);
	int DepthGetter(BiTreeNode<T> *pNode);
	void PrintTreeRecursion(BiTreeNode<T> *pNode, int level);
	void DestroyTree(BiTreeNode<T> *pNode);
private:
	BiTreeNode<T> *pRootNode;
};



